#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <stack>
// 时间复杂度为O(N*logN)
// 空间复杂度为O(logN)
// 不稳定的
// // 方法一数组分三块+随机数选key
// int getRandom(std::vector<int> &nums, int left, int right)
// {
//     int x = rand();
//     return nums[x % (right - left + 1) + left];
// }
// void quickSort(std::vector<int> &nums, int l, int r)
// {
//     if (l >= r)
//         return;

//     int key = getRandom(nums, l, r);
//     // 数组分三块
//     int i = l, left = l - 1, right = r + 1;
//     while (i < right)
//     {
//         if (nums[i] < key)
//             std::swap(nums[++left], nums[i++]);
//         else if (nums[i] == key)
//             i++;
//         else
//             // 注意这里i不++
//             std::swap(nums[--right], nums[i]);
//     }

//     //  [l, left] [left + 1, right - 1] [right, r]
//     quickSort(nums, l, left);
//     quickSort(nums, right, r);
// }

// 三数取中
int GetMidIndex(std::vector<int> &nums, int left, int right)
{
    int mid = (right - left) / 2 + left;
    if (nums[left] < nums[mid])
    {
        // nums[left] < nums[mid] < nums[right]
        if (nums[mid] < nums[right])
        {
            return mid;
        }
        // nums[mid]最大
        else if (nums[left] > nums[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    // nums[left] > nums[mid]
    else
    {
        // nums[mid] < nums[left] < nums[right]
        if (nums[left] < nums[right])
        {
            return left;
        }
        // nums[left]最大
        else if (nums[mid] > nums[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
}

// hoare法
int partSort1(std::vector<int> &nums, int left, int right)
{
    // 三数取中
    int mid = GetMidIndex(nums, left, right);
    std::swap(nums[left], nums[mid]);
    int keyi = left;

    while (left < right)
    {
        // R找小
        // left < right,避免left和right错过或者越界
        // >= 避免死循环
        while (left < right && nums[right] >= nums[keyi])
        {
            right--;
        }
        // L找大
        while (left < right && nums[left] <= nums[keyi])
        {
            left++;
        }

        std::swap(nums[left], nums[right]);
    }

    int meeti = left;
    std::swap(nums[meeti], nums[keyi]);

    return meeti;
}

// 挖坑法
int partSort2(std::vector<int> &nums, int left, int right)
{
    int mid = GetMidIndex(nums, left, right);
    std::swap(nums[left], nums[mid]);

    int key = nums[left];
    int hole = left;

    while (left < right)
    {
        // 右边找小，填到左边坑
        while (left < right && nums[right] >= key)
        {
            right--;
        }
        nums[hole] = nums[right];
        hole = right;

        // 左边找大，填到右边坑
        while (left < right && nums[left] <= key)
        {
            left++;
        }

        nums[hole] = nums[left];
        hole = left;
    }

    nums[hole] = key;
    return hole;
}

int partSort3(std::vector<int> &nums, int left, int right)
{
    int mid = GetMidIndex(nums, left, right);
    std::swap(nums[left], nums[mid]);

    int keyi = left;
    int prev = left;
    int cur = left + 1;

    // while (cur <= right)
    // {
    //     while(cur <= right && nums[cur] < nums[keyi])
    //         std::swap(nums[++prev],nums[cur++]);
    //     while (cur <= right && nums[cur] >= nums[keyi])
    //     {
    //         cur++;
    //     }
    // }

    while (cur <= right)
    {
        while (cur <= right && nums[cur] >= nums[keyi])
        {
            cur++;
        }
        while (cur <= right && nums[cur] < nums[keyi])
            std::swap(nums[++prev], nums[cur++]);
    }

    // while (cur <= right)
    // {
    // 	// 找小
    // 	if (nums[cur] < nums[keyi] && ++prev != cur)
    // 	{
    // 		std::swap(nums[prev], nums[cur]);
    // 	}

    // 	++cur;
    // }

    std::swap(nums[keyi], nums[prev]);
    return prev;
}

void quickSort(std::vector<int> &nums, int begin, int end)
{
    if (begin >= end)
        return;

    int keyi = partSort3(nums, begin, end);

    quickSort(nums, begin, keyi - 1);
    quickSort(nums, keyi + 1, end);
}

void QuickSortNonR(std::vector<int> &nums, int begin, int end)
{
    std::stack<int> st;
    st.push(begin);
    st.push(end);

    while (st.size())
    {
        int right = st.top();
        st.pop();

        int left = st.top();
        st.pop();

        // [left, keyi-1] keyi [keyi+1,right]
        int keyi = partSort3(nums, left, right);

        if (left < keyi - 1)
        {
            st.push(left);
            st.push(keyi - 1);
        }
        if (keyi + 1 < right)
        {
            st.push(keyi + 1);
            st.push(right);
        }
    }
}